# coding=utf-8
from collections import deque

from python.unit6_tree.part1_basic.Node import Node
from python.unit6_tree.part1_basic.Tree import Tree


#  构造bst树
class SortedArrayToBST:
    def sortedArrayToBST(self, nums):
        return self.helper(0, len(nums) - 1, nums)

    def helper(self, left, right, nums):
        if left > right:
            return None

        # 总是选择中间位置左边的数字作为根节点
        mid = (left + right) // 2
        root = Node(nums[mid])
        root.left = self.helper(left, mid - 1, nums)
        root.right = self.helper(mid + 1, right, nums)
        return root


if __name__ == "__main__":
    tree = Tree()
    nums = [0, -10, 5, None, -3, None, 9]
    root = tree.init_tree_for_bst_search()
    sortedArrayToBST = SortedArrayToBST()
    res = sortedArrayToBST.sortedArrayToBST(nums)
